package DP;

import java.util.*;
/**
 * 322.零钱兑换  （完全背包：装满背包最少物品数）
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 * dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
 * dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
 */
public class coinChange {

    /**
     * 一刷，二刷思路一致，不做记录
     */
    public int coinChange1(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
    public int coinChange(int[] coins, int amount) {
        // 初始化二维dp数组，行数为coins的数量，列数为amount + 1
        int[][] dp = new int[coins.length + 1][amount + 1];

        // 初始化dp数组：dp[i][0] 都应该为0，因为凑成0元不需要硬币
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 0;
        }

        // 初始化其他dp[i][j]，为amount + 1，这是一个不可能达到的较大值
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = amount + 1; // 初始化为不可能值
            }
        }

        // 动态规划填表
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                // 不使用当前硬币coins[i-1]，直接继承前一个状态
                dp[i][j] = dp[i-1][j];
                // 使用当前硬币coins[i-1]，并且金额大于等于当前硬币面值
                if (j >= coins[i-1]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i-1]] + 1);
                }
            }
        }

        // 如果dp[coins.length][amount] 仍然是初始化的值，则返回-1，表示无法凑成该金额
        return dp[coins.length][amount] > amount ? -1 : dp[coins.length][amount];
    }

    /**
     * hot100一刷
     */
    class Solution {
        public int coinChange(int[] coins, int amount) {
            int dp[] = new int[amount + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for (int i = 0; i < coins.length; i++) {
                for (int j = coins[i]; j <= amount; j++) {
                    if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                        dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                    }
                }
            }
            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
        }
    }
}
